package com.arithmetic;

public class SortTest {
	public static void printArray(int[] array) {  
		System.out.print("{");  
		for (int i = 0; i < array.length; i++) {  
			System.out.print(array[i]);  
			if (i < array.length - 1) {  
				System.out.print(", ");  
			}  
		}  
		System.out.println("}");  
	}
	
	public static void mt1(){
		int a[] = {23, 5, 83, 3, 1, 66, 44};
		for(int i=a.length-1; i>0; i--){
			for(int j=0; j<i; j++){
				if(a[j] > a[j + 1]){
					int temp = a[j];
					a[j] = a[j+1];
					a[j + 1] = temp;
				}
			}
		}
		printArray(a);
	}
	
	public static void mt2(){
		int a[] = {23, 5, 83, 3, 1, 66, 44};
		int k=0;
		for(int i=0; i<a.length - 1; i++){
			k=i;
			for(int j=i; j<a.length; j++){
				if(a[k] > a[j]){
					k = j;
				}
			}
			
			if(k != i){
				int temp = a[k];
				a[k] = a[i];
				a[i] = temp;
			}
		}
		printArray(a);
	}
	
	public static void mt3(){
		int a[] = {23, 15, 83, 3, 1, 66, 44};
		int sentinel;
		for(int i=1; i<a.length; i++){
			int j = i - 1;
			sentinel = a[j + 1];
			while(j >= 0 && sentinel < a[j]){
				a[j + 1] = a[j];
				j--;
			}
			
			if(j != i - 1){
				a[j + 1] = sentinel;
			}
		}
		printArray(a);
	}
	
	/*----------------------------------------------------------------------------------*/
	public static void mt4(){
		int a[] = {23, 15, 83, 3, 1, 66, 44};
		int sentinel, j;
		for(int increment=a.length / 2; increment>0; increment/=2){
			for(int i=increment; i<a.length; i++){
				j = i - increment;
				sentinel = a[i];
				while(j >= 0 && sentinel < a[j]){
					a[j + increment] = a[j];
					j -= increment;
				}
				a[j + increment] = sentinel;
			}
		}
		printArray(a);
	}
	
	public static void quickSort(int a[], int left, int right){
		if(left < right){
			int dp = partition(a, left, right);
			quickSort(a, left, dp - 1);
			quickSort(a, dp + 1, right);
		}
	}
	
	public static int partition(int a[], int left, int right){
		int sentinel = a[left];
		while(left < right){
			while(left<right && a[right]>sentinel){
				right --;
			}
			a[left] = a[right];
			while(left<right && a[left] <sentinel){
				left ++;
			}
			a[right] = a[left];
		}
		a[left] = sentinel;
		return left;
	}
	
	public static void mt5(){
		int a[] = {23, 15, 83, 3, 1, 66, 44, 69};
		quickSort(a, 0, a.length - 1);
		printArray(a);
	}
	
	/*----------------------------------------------------------------------------------*/
	public static void heapSort(int[] array) {
		buildHeap(array);// 构建堆
		int n = array.length;
		int i = 0;
		for (i = n - 1; i >= 1; i--) {
			swap(array, 0, i);
			heapify(array, 0, i);
		}
	}
	
	public static void buildHeap(int[] array) {
		int n = array.length;// 数组中元素的个数
		for (int i = n / 2 - 1; i >= 0; i--)
			heapify(array, i, n);
	}

	public static void heapify(int[] A, int idx, int max) {
		int left = 2 * idx + 1;// 左孩子的下标（如果存在的话）
		int right = 2 * idx + 2;// 右孩子的下标（如果存在的话）
		int largest = 0;// 寻找3个节点中最大值节点的下标
		if (left < max && A[left] > A[idx])
			largest = left;
		else
			largest = idx;
		if (right < max && A[right] > A[largest])
			largest = right;
		if (largest != idx) {
			swap(A, largest, idx);
			heapify(A, largest, max);
		}
		System.out.println();
		printArray(A);
	}

	public static void swap(int[] array, int i, int j) {
		int temp = 0;
		temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	} 
	/*----------------------------------------------------------------------------------*/
	public static void main(String[] args) {
		
	}
}
